/*  untangling.cpp
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "untangling.h"

bool untangle(vector<Point*> & ch1, vector<Point*> & ch2) {
  list<Point*> l1,l2;
  l1.insert(l1.begin(),ch1.begin(),ch1.end());
  l2.insert(l2.begin(),ch2.begin(),ch2.end());
  bool ret=false;
  for(list<Point*>::iterator it1=l1.begin(); it1!=l1.end(); it1++) {
    for(list<Point*>::iterator it2=l2.begin(); it2!=l2.end(); it2++) {
      list<Point*>::iterator it1p = it1;
      it1p++;
      list<Point*>::iterator it2p = it2;
      it2p++;
      if(it1p==l1.end() || it2p==l2.end()) break;
      if(cross(*it1,*it1p,*it2,*it2p) 
          || between(*it1,*it1p,*it2) || between(*it1,*it1p,*it2p)
          || between(*it2,*it2p,*it1) || between(*it2,*it2p,*it1p)) {

        list<Point*> tail1;
        tail1.insert(tail1.begin(),it1p,l1.end());
        l1.erase(it1p,l1.end());

        list<Point*> tail2;
        tail2.insert(tail2.begin(),it2p,l2.end());
        l2.erase(it2p,l2.end());

        l1.insert(l1.end(),tail2.begin(),tail2.end());
        l2.insert(l2.end(),tail1.begin(),tail1.end());
        ret=true;
      }
    }
  }
  if(ret) {
    ch1.clear();
    ch1.insert(ch1.begin(),l1.begin(),l1.end());
    ch2.clear();
    ch2.insert(ch2.begin(),l2.begin(),l2.end());
    PointXCmpDes cmp;
    sort(ch1.begin(),ch1.end(),cmp);
    sort(ch2.begin(),ch2.end(),cmp);
  }
  return ret;
}

void untangle2(vector<Point*> & chain1, vector<Point*> & chain2) {

  list<Point*> chainl1(chain1.begin(), chain1.end());
  list<Point*> chainl2(chain2.begin(), chain2.end());
  list<Point*>::iterator it1 = chainl1.begin();
  list<Point*>::iterator it2 = chainl2.begin();
  Point * p1, *p2, *p3, *p4;
  p1 = *it1++;
  p3 = *it2++;
  p2 = *it1;
  p4 = *it2;

  while(it1!=chainl1.end() && it2!=chainl2.end()) {
    if(cross(p1,p2,p3,p4) || (between(p1,p2,p3) && left(p1,p2,p4))) {
      it2 = chainl2.erase(it2);
      it1 = chainl1.insert(it1, p4);
      it1++;
      p3 = p4;
      p4 = *it2;
      while(!cross(p1,p2,p3,p4) && left(p1,p2,p4)) {
        it2 = chainl2.erase(it2);
        it1 = chainl1.insert(it1, p4);
        it1++;
        if(it2==chainl2.end()) {
          cout << "Didn't cross back." << endl;
          exit(-1);
        }
        p3 = p4;
        p4 = *it2;
      }
      it2++;
      p3 = p4;
      p4 = *it2;
    } else if(p4->getX() > p2->getX()) {
      p1 = p2;
      it1++;
      p2 = *it1;
    } else {
      p3 = p4;
      it2++;
      p4 = *it2;
    }
  }  

  chain1 = vector<Point*>(chainl1.begin(),chainl1.end());
  chain2 = vector<Point*>(chainl2.begin(),chainl2.end());
}

vector<vector<Point*>*> untangle(vector<vector<Point*>*> chains) {
  if(chains.size()==0) return chains;
  /*for(size_t i=chains.size()-1;i>0;i--) 
    for(size_t j=i-1;j+1!=0;j--) 
      untangle2(*(chains[i]),*(chains[j]));*/
  bool tangle=true;
  while(tangle) {
    tangle = false;
    for(size_t i=chains.size()-1;i>0;i--) {
      for(size_t j=i-1;j+1!=0;j--) {
        //cout << "untangling chains " << i << " and " << j << endl;
        tangle |= untangle(*(chains[i]),*(chains[j]));
      }
    }
    //break;
  }
  PointXCmpDes cmp;
  for(size_t i=0;i<chains.size();i++)
    sort(chains[i]->begin(),chains[i]->end(),cmp);
  for(size_t i=chains.size()-1;i>0;i--) {
    for(size_t j=i-1;j+1!=0;j--) {
      if(!checkUntangled(*(chains[i]),*(chains[j]))) {
        cout << "1) chain " << i << " crosses with " << j << endl;
        stringstream ss1;
        ss1 << "chain" << i << ".dat";
        ofstream ch1(ss1.str().c_str());
        for(size_t k=0;k<chains[i]->size();k++)
          ch1 << chains[i]->at(k) << endl;
        ch1.close();
        stringstream ss2;
        ss2 << "chain" << j << ".dat";
        ofstream ch2(ss2.str().c_str());
        for(size_t k=0;k<chains[j]->size();k++)
          ch2 << chains[j]->at(k) << endl;
        ch2.close();
        exit(-1);
      }
    }
  }
  return chains;
}


bool checkUntangled(vector<Point*> & chain1, vector<Point*> & chain2) {
  for(size_t i=0;i<chain1.size()-1;i++) {
    for(size_t j=0;j<chain2.size()-1;j++) {
      if(cross(chain1[i],chain1[i+1],chain2[j],chain2[j+1]))
        return false;
      /*if(between(chain1[i],chain1[i+1],chain2[j]) || between(chain1[i],chain1[i+1],chain2[j+1])) 
        return false;
      if(between(chain2[j],chain2[j+1],chain1[i]) || between(chain2[j],chain2[j+1],chain1[i+1]))
        return false;*/
    }
  }
  return true;
}

